W6. Детерминированные автоматы с магазином, конфигурации, лемма о накачке для КС-языков, автоматы с магазином и компиляторы

Автор

Manuel Mazzara

Дата публикации

26 февраля 2026 г.

1. Краткое содержание

1.1 От конечных автоматов к автоматам с магазином

Мы уже знаем, что конечные автоматы (FSA) распознают регулярные языки. Но у FSA есть фундаментальное ограничение: у них есть лишь фиксированная конечная память — по сути только текущее состояние. Из-за этого некоторые языки распознать нельзя, например $L = \{a^n b^n \mid n \geq 0\}$: машине пришлось бы помнить произвольно большое число символов a.

Чтобы выйти за пределы регулярных языков, нужна модель с большей памятью. Естественное расширение — «прицепить» к FSA магазин (стек), получив автомат с магазином (PDA). Название «pushdown» отражает именно природу стека: новые элементы кладутся сверху, а снимается всегда верхний.

От FSA к PDA: тот же конечный контроллер получает неограниченный стек

Неформально:

FSA = блок конечного управления (только состояния)
PDA = блок конечного управления + бесконечный стек

Иерархия моделей вычислений (от более слабой к более сильной) выглядит так:

Комбинационная логика — без памяти
Конечные автоматы (FSA) — фиксированная ограниченная память (фактически только текущее состояние)
Автоматы с магазином (PDA) — неограниченная память в виде стека (может расти без предела)
Машины Тьюринга — полноценная лента для чтения/записи (максимальная мощность)

PDA находятся ровно на ступень выше FSA и распознают контекстно-свободные языки (КС-языки, CFL), к которым относится большинство синтаксических конструкций языков программирования. Поэтому PDA — в центре компиляции: синтаксис языков программирования контекстно-свободен.

1.2 Стек: краткое напоминание

Стек — структура данных «последним пришёл — первым ушёл» (LIFO). Представьте стопку подносов в столовой: добавлять и снимать можно только сверху.

Дисциплина стека LIFO, которую используют PDA

Операции:

Push: положить новый символ на вершину стека.
Pop: снять верхний символ со стека (и одновременно «прочитать» его).

У PDA стек изначально содержит особый символ дна стека $Z_0$, который играет роль сторожевого маркера низа. Когда сверху $Z_0$, стек можно считать «пустым».

Пример — push $a$, $b$, $c$, затем pop:

Начальный стек: только $Z_0$ внизу
Push $a$: стек = $a, Z_0$ (сверху вниз)
Push $b$: стек = $b, a, Z_0$
Push $c$: стек = $c, b, a, Z_0$
Pop: снимаем $c$; стек = $b, a, Z_0$

Последним положенный символ всегда снимается первым. Это свойство LIFO делает стек удобным для сопоставления вложенных структур вроде сбалансированных скобок.

Историческая справка: идею стека ввёл Алан Тьюринг в работе 1946 года об Automatic Computing Engine (ACE); операции он называл BURY и UNBURY и использовал их в теории подпрограмм.

1.3 Неформальное описание PDA

У PDA три компонента:

Входная лента — только для чтения, слева направо (входная строка)
Блок конечного управления — как у FSA, хранит текущее состояние
Стек неограниченного размера — дополнительная память; контроллер читает вершину и заменяет её

Шаг PDA: прочитать вход, посмотреть вершину стека, перейти к новой конфигурации

На каждом шаге PDA одновременно смотрит на три вещи:

Текущее состояние $q$
Следующий входной символ (или $\varepsilon$ для «тихого» шага)
Вершину стека

Исходя из этой тройки, он:

Переходит в новое состояние $q'$
Сдвигает головку по входу (или остаётся на месте при $\varepsilon$-переходе)
Заменяет верхний символ стека на строку $\alpha \in \Gamma^*$

С помощью стека PDA может:

Кладуть (push) символы на стек (заменить верх $A$ на $BA$, тогда $B$ сверху)
Снимать (pop) верхний символ (заменить верх $A$ на $\varepsilon$)
Не менять стек (заменить верх $A$ на $A$)
Делать $\varepsilon$-переходы — переходы без чтения входа, только со изменением стека

Критерий принятия: строка принимается, если после полного чтения PDA находится в принимающем (финальном) состоянии. Содержимое стека в конце для принятия финальным состоянием не важно.

1.4 Формальное определение PDA

Автомат с магазином (PDA) — это 7-кортеж:

\[P = (Q,\, I,\, \Gamma,\, \delta,\, q_0,\, Z_0,\, F)\]

где:

$Q$ — конечное множество состояний
$I$ — конечный входной алфавит (символы, читаемые с ленты)
$\Gamma$ — конечный алфавит магазина (символы, которые могут лежать на стеке; $I$ и $\Gamma$ могут пересекаться)
$\delta: Q \times (I \cup \{\varepsilon\}) \times \Gamma \to \mathcal{P}(Q \times \Gamma^*)$ — функция переходов (частичное отображение в множество возможных исходов)
$q_0 \in Q$ — начальное состояние
$Z_0 \in \Gamma$ — начальный символ стека (маркер дна, кладётся на стек в начале)
$F \subseteq Q$ — множество принимающих (финальных) состояний

Как читать функцию переходов: переход $\delta(q, a, A) \ni (q', \alpha)$ означает:

В состоянии $q$, читая входной символ $a$ (или $\varepsilon$), при вершине стека $A$: перейти в $q'$ и заменить $A$ строкой $\alpha$.

На стрелках в диаграммах пишут: $a,\, A / \alpha$ — «прочитать $a$ с входа, снять $A$ со стека, положить $\alpha$».

Чтобы положить $B$ под $A$: $A / BA$ (заменить $A$ на $BA$; теперь сверху $B$)
Чтобы снять $A$: $A / \varepsilon$
Чтобы оставить стек неизменным: $A / A$

Ограничения на $Z_0$:

На стеке всегда есть хотя бы $Z_0$
$Z_0$ никогда не удаляется со стека
Не кладутся дополнительные копии $Z_0$ на стек

1.5 Детерминированные автоматы с магазином (DPDA)

Общий PDA выше недетерминированен: $\delta(q, a, A)$ может содержать несколько пар, то есть «выбор» между переходами. Недетерминированные PDA (NPDA) — мощный инструмент, но на практике компиляторы используют детерминированные PDA.

PDA $M = (Q, I, \Gamma, \delta, q_0, Z_0, F)$ — детерминированный автомат с магазином (DPDA), если выполняются оба условия:

Не больше одного перехода на шаг: для всех $q \in Q$, $x \in I \cup \{\varepsilon\}$ и $\gamma \in \Gamma$ множество $\delta(q, x, \gamma)$ содержит не более одного элемента.
Нет конфликта между чтением входа и $\varepsilon$-переходами: для всех $q \in Q$, $x \in I$ и $\gamma \in \Gamma$ множества $\delta(q, x, \gamma)$ и $\delta(q, \varepsilon, \gamma)$ не могут быть оба непустыми.

Второе условие: если есть $\varepsilon$-переход из $q$ при вершине $\gamma$, то не должно быть перехода с чтением входа из того же $q$ при той же вершине $\gamma$. Так устраняется неоднозначность «читать вход или сделать спонтанный шаг».

Зачем нужно правило про $\varepsilon$: если бы одновременно $\delta(q, a, A)$ и $\delta(q, \varepsilon, A)$ были непусты, автомат был бы недетерминирован — он мог бы либо съесть $a$, либо сделать спонтанный шаг. DPDA такую двусмысленность запрещают.

Практическое соглашение: часто используют $\varepsilon, Z_0 / Z_0$ как финальный переход в принимающее состояние, когда весь вход прочитан и на стеке остался только $Z_0$.

1.6 Конфигурации и переходы

Чтобы формально описать работу PDA, вводят конфигурацию.

1.6.1 Конфигурация

Конфигурация — «мгновенный снимок» PDA в данный момент. В нём зафиксировано всё, что нужно для продолжения вычисления:

\[c = (q, x, \gamma)\]

где:

$q \in Q$ — текущее состояние управляющего устройства
$x \in I^*$ — непрочитанный фрагмент входной строки
$\gamma \in \Gamma^*$ — текущее содержимое стека (от верха к низу)

Соглашение: стек записывается сверху вниз. Если $\gamma = A\beta$, то $A$ — вершина, $\beta$ — всё ниже.

Пример: конфигурация $c = (q_1, abbb, ABZ_0)$ означает: автомат в состоянии $q_1$, непрочитанный вход — $abbb$, на стеке (сверху вниз) лежат $A$, $B$, $Z_0$.

Начальная конфигурация: $(q_0, x, Z_0)$ для любой входной строки $x$.

1.6.2 Переходы между конфигурациями

Символ $\vdash$ («выводит за один шаг», «переходит к») описывает один шаг. Есть два случая:

Случай 1 — чтение входного символа: если $\delta(q, a, A) = (q', \alpha)$ определена, а в текущей конфигурации на вершине $A$, а непрочитанный вход начинается с $ax$, то:

\[(q,\; ax,\; A\beta) \;\vdash\; (q',\; x,\; \alpha\beta)\]

Словами: съесть $a$ со входа, снять $A$ со стека, положить $\alpha$, перейти в $q'$.

Случай 2 — $\varepsilon$-переход (спонтанный): если $\delta(q, \varepsilon, A) = (q', \alpha)$ определена и на вершине $A$:

\[(q,\; x,\; A\beta) \;\vdash\; (q',\; x,\; \alpha\beta)\]

Словами: не читать вход, снять $A$, положить $\alpha$, перейти в $q'$.

Ключевая разница: в случае 1 головка входа сдвигается на один символ; в случае 2 остаётся на месте.

**1.6.3 Многошаговое вычисление: $\vdash^*$**

$\vdash^*$ — рефлексивное транзитивное замыкание $\vdash$. То есть $c_1 \vdash^* c_k$ означает, что есть цепочка из нуля или более шагов:

\[c_1 \vdash c_2 \vdash c_3 \vdash \cdots \vdash c_k\]

Отношение $\vdash^*$ описывает полный путь вычисления между конфигурациями.

1.6.4 Принятие строки PDA

Строка $x \in I^*$ принимается PDA $M = (Q, I, \Gamma, \delta, q_0, Z_0, F)$, если:

\[(q_0,\; x,\; Z_0) \;\vdash^*\; (q,\; \varepsilon,\; \gamma)\]

для некоторого $q \in F$ и некоторого $\gamma \in \Gamma^*$.

Проще говоря: из начальной конфигурации (состояние $q_0$, весь вход $x$, на стеке только $Z_0$) можно дойти до конфигурации, где:

Весь вход прочитан (непрочитанное — $\varepsilon$)
Текущее состояние принимающее ($q \in F$)
Стек может быть любым ($\gamma$ произволен)

Язык, распознаваемый $M$:

\[L(M) = \{x \in I^* \mid (q_0, x, Z_0) \vdash^* (q, \varepsilon, \gamma) \text{ для некоторых } q \in F, \gamma \in \Gamma^*\}\]

1.7 Два режима принятия

PDA может принимать строку двумя способами:

Принятие финальным состоянием: вход полностью прочитан и автомат в состоянии $q \in F$. Содержимое стека не важно.
Принятие пустым стеком: вход полностью прочитан и на стеке только $Z_0$ (фактически «пусто»). Состояние не важно.

Для недетерминированных PDA эти режимы эквивалентны: любой язык, принимаемый одним способом, можно принять и другим (построив другой PDA). Для детерминированных PDA режимы не эквивалентны.

Тонкость про пустой стек: языки, принимаемые пустым стеком, должны быть беспрефиксными (prefix-free): ни одна строка языка не является собственным префиксом другой. Как только стек «опустел» на $w$, продолжить разбор продолжения $wz$ уже нельзя.

1.8 Разобранный пример: PDA для $L = \{a^n b^n \mid n \geq 1\}$

Классический пример: как PDA «считает» с помощью стека.

Стратегия: для каждого входного a положить на стек один символ $A$. Когда начинаются b, снимать по одному $A$ на каждый b. Если ровно в момент, когда все b кончились, на стеке только $Z_0$, счётчики совпали.

Спецификация PDA:

Состояния: $p_0$ (старт), $p_1$ (чтение a), $p_2$ (чтение b), $p_3$ (принятие)
Алфавит стека: $\Gamma = \{Z_0, A\}$
Переходы:

Переход	Запись	Смысл
$p_0 \to p_1$	$a,\, Z_0 / AZ_0$	Первый `a`; положить $A$ над $Z_0$
$p_1 \circlearrowleft$	$a,\, A / AA$	Каждый следующий `a`; ещё один $A$
$p_1 \to p_2$	$b,\, A / \varepsilon$	Первый `b`; снять один $A$
$p_2 \circlearrowleft$	$b,\, A / \varepsilon$	Каждый следующий `b`; снять $A$
$p_2 \to p_3$	$\varepsilon,\, Z_0 / Z_0$	Вход исчерпан; сверху $Z_0$ — значит все $A$ совпали; принять

Трассировка для входа "aabb":

Шаг	Состояние	Непрочитанный вход	Стек (сверху вниз)	Правило
1	$p_0$	$\mathbf{a}abb$	$Z_0$	$a,\, Z_0 / AZ_0$: push $A$
2	$p_1$	$\mathbf{a}bb$	$A, Z_0$	$a,\, A / AA$: push $A$
3	$p_1$	$\mathbf{b}b$	$A, A, Z_0$	$b,\, A / \varepsilon$: pop $A$
4	$p_2$	$\mathbf{b}$	$A, Z_0$	$b,\, A / \varepsilon$: pop $A$
5	$p_2$	$\varepsilon$	$Z_0$	$\varepsilon,\, Z_0 / Z_0$: к принятию
6	$p_3$	$\varepsilon$	$Z_0$	ПРИНЯТО $\checkmark$

Полное вычисление: \[(p_0, aabb, Z_0) \vdash (p_1, abb, AZ_0) \vdash (p_1, bb, AAZ_0) \vdash (p_2, b, AZ_0) \vdash (p_2, \varepsilon, Z_0) \vdash (p_3, \varepsilon, Z_0)\]

1.9 Ещё примеры PDA

1.9.1 PDA для $L_2 = \{a^n b a^n \mid n \in \mathbb{N}^+\}$

Стратегия: положить по одному $A$ на каждый a до единственного b. Символ b — «перекрёсток». После b снимать по одному $A$ на каждый a справа. Если в конце входа стек дошёл до $Z_0$, блоки a слева и справа одинаковой длины.

Состояния: $q_0$ (старт, фаза push), $q_1$ (фаза pop после b), $q_2$ (принятие)
Переходы:

Переход	Запись	Смысл
$q_0 \circlearrowleft$	$a,\, Z_0 / AZ_0$	Первый `a` до `b`: push $A$
$q_0 \circlearrowleft$	$a,\, A / AA$	Каждый следующий `a` до `b$: push $A$ \| \| $q_0 \to q_1$ \| $b,\, A / A$ \| Видим`b`; стек не меняем, меняем состояние \| \| $q_1 \circlearrowleft$ \| $a,\, A / \varepsilon$ \| Каждый`a`после`b`: pop один $A$
$q_1 \to q_2$	$\varepsilon,\, Z_0 / Z_0$	Все $A$ совпали; принять

**1.9.2 PDA для $L_3 = \{vcv^R \mid v \in \{a,b\}^*\}$**

Язык $L_3$ состоит из строк вида $v \cdot c \cdot v^R$: строка $v$, маркер центра $c$, затем $v$ в обратном порядке. Символ $c$ — «осевая опора».

Стратегия: вся $v$ кладётся на стек. Прочитав $c$, переключиться в режим pop: для каждого символа $v^R$ снимать согласованный символ со стека. Если после всего входа вернулись к $Z_0$ — принять.

Состояния: $q_0$ (фаза push), $q_1$ (фаза pop после $c$), $q_2$ (принятие)
Ключевые переходы (фаза push, состояние $q_0$, петли):
- $a,\, Z_0 / AZ_0$; $b,\, Z_0 / BZ_0$; $a,\, A / AA$; $a,\, B / AB$; $b,\, A / BA$; $b,\, B / BB$
Опора (при чтении $c$): $c,\, A / A$; $c,\, B / B$; $c,\, Z_0 / Z_0$ (все ведут $q_0 \to q_1$)
Фаза pop ($q_1$, петли): $a,\, A / \varepsilon$; $b,\, B / \varepsilon$
Принятие: $\varepsilon,\, Z_0 / Z_0$ ($q_1 \to q_2$)

1.9.3 PDA для сбалансированных круглых скобок

Язык сбалансированных (корректно вложенных) скобок — типичный контекстно-свободный язык. Интуитивно каждой ( нужна парная ), пары должны быть правильно вложены.

Состояния: $q_0$ (старт), $q_1$ (работа), $q_2$ (принятие)
Переходы:
- $q_0 \to q_1$: $(,\, Z_0 / PZ_0$ — первая (: push $P$
- $q_1 \circlearrowleft$: $(,\, P / PP$ — каждая следующая (: push $P$
- $q_1 \circlearrowleft$: $),\, P / \varepsilon$ — каждая ): pop один $P$ (сопоставление с ()
- $q_1 \to q_2$: $\varepsilon,\, Z_0 / Z_0$ — вход кончился, «пустой» стек: принять

1.10 PDA и FSA: общая картина

Каждый регулярный язык распознаётся PDA (достаточно симулировать FSA, не используя стек).
PDA распознают языки, которые FSA не распознают (например, $a^n b^n$).
Значит, класс контекстно-свободных языков строго шире класса регулярных.

Классический PDA для aⁿbⁿ

Регулярные языки $\subsetneq$ языки, распознаваемые PDA (контекстно-свободные)
Примеры КС, но не регулярных: $a^n b^n$, $vcv^R$, сбалансированные скобки
Примеры сильнее PDA: $a^n b^n c^n$ (нужно считать три величины одновременно — одного стека недостаточно)

Память:

FSA: фиксированная ограниченная память (только состояние — фиксированное число бит)
PDA: конечное управление, но не фиксированный объём памяти — стек может расти неограниченно
Ключевая мысль: регулярные языки про ограниченную память; контекстно-свободные требуют неограниченной памяти (но со специфической структурой LIFO)

1.11 PDA и компиляторы

PDA напрямую связаны с тем, как устроены современные компиляторы. Компилятор переводит исходный код (например, C, Python) в другой язык (например, машинный). Он состоит из нескольких фаз:

Регулярные языки — собственное подмножество контекстно-свободных

Лексический анализ: разбивает исходный текст на лексемы (tokens) — минимальные осмысленные единицы (ключевые слова, идентификаторы, операторы и т.д.). Синтаксис лексем регулярный, поэтому эту фазу выполняет FSA (или движок регулярных выражений).
Синтаксический анализ (разбор): проверяет, что последовательность токенов соответствует грамматике языка. В языках программирования есть вложенные структуры (сбалансированные скобки, вызовы функций, арифметические выражения) — это контекстно-свободно. Эту фазу выполняет PDA.
Семантический анализ: типы, область видимости и т.п.
Генерация и оптимизация кода: построение и улучшение целевого кода.

Почему разбор — это PDA? В языках есть конструкции, требующие согласованных/вложенных структур:

блоки {...} в C/Java
begin...end в Pascal
арифметические выражения в скобках
вложенные вызовы функций

Именно то, с чем PDA справляются, а FSA — нет.

Лексический анализ на FSA, потому что токены (идентификаторы, числа, ключевые слова) описываются регулярными шаблонами. Например, идентификатор в Pascal соответствует регулярной схеме <letter>(<letter>|<digit>)*, что легко распознать FSA.

Синтаксический анализ на PDA, потому что правила вроде «выражение — это терм, затем оператор, затем другое выражение, возможно со скобками» — контекстно-свободны.

«Контекстно-свободные грамматики с 1960-х играют центральную роль в технологии компиляторов… Существует автоматная нотация, называемая ‘автомат с магазином’, которая описывает ровно все и только контекстно-свободные языки.» — Джон Е. Хопкрофт, Раджив Мотвани и Джеффри Д. Ульман

1.12 Лемма о накачке для КС-языков (лемма Бар-Хиллеля)

Как лемма о накачке для регулярных языков помогает доказывать нерегулярность, так и для КС-языков есть аналог.

1.12.1 Лемма о накачке для регулярных языков (напоминание)

Лемма о накачке (FSA): если $L \subseteq \Sigma^*$ — регулярный язык, то существует $m \geq 1$ такое, что любое $w \in L$ с $|w| \geq m$ можно записать как $w = xyz$, где:

$y \neq \varepsilon$ (т.е. $|y| \geq 1$)
$|xy| \leq m$
$xy^i z \in L$ для любого $i \geq 0$

Контрапозиция — рабочий инструмент: если для некоторого слова из $L$ нет такого разбиения, то $L$ не регулярен.

1.12.2 Лемма Бар-Хиллеля (лемма о накачке для КС-языков)

Лемма Бар-Хиллеля: если $L \subseteq I^*$ — контекстно-свободный язык (распознаётся PDA), то существует $m \geq 1$ такое, что любое $w \in L$ с $|w| \geq m$ можно записать как $w = x_1 x_2 x_3 x_4 x_5$, где:

$|x_2 x_4| > 0$ (хотя бы один из $x_2$, $x_4$ непуст)
$|x_2 x_3 x_4| \leq m$ («средняя» часть не слишком длинная)
$x_1 x_2^i x_3 x_4^i x_5 \in L$ для любого $i \geq 0$ (одновременная накачка $x_2$ и $x_4$ одинаковым числом повторов сохраняет строку в $L$)

Главное отличие от регулярной леммы: в регулярном случае качают один отрезок $y$. В КС-случае качают два отрезка ($x_2$ и $x_4$) синхронно — одинаковое число повторов $i$.

Наглядная связь с деревьями разбора (нормальная форма Хомского): в достаточно высоком дереве разбора какой-то нетерминал $N$ повторяется. Два «рукава» от двух вхождений $N$ дают два накачиваемых отрезка $x_2$ и $x_4$.

Интуиция Бар-Хиллеля: повтор нетерминала порождает два накачиваемых поддерева

1.12.3 Контрапозиция: как доказать «не КС»

Следствие (форма для доказательства): если для любого $m \geq 1$ существует $w \in L$ с $|w| \geq m$ такое, что для каждого разбиения $w = x_1 x_2 x_3 x_4 x_5$ с $|x_2 x_4| > 0$ и $|x_2 x_3 x_4| \leq m$ найдётся $i \geq 0$, для которого $x_1 x_2^i x_3 x_4^i x_5 \notin L$, то $L$ не контекстно-свободен (ни один PDA его не распознаёт).

Игра в двух лицах:

Игрок 1 (противник)	Игрок 2 (вы)
Выбирает любое $m \geq 1$	Выбираете $w \in L$ с $\|w\| \geq m$
Выбирает разбиение $w = x_1 x_2 x_3 x_4 x_5$ с $\|x_2 x_4\| > 0$ и $\|x_2 x_3 x_4\| \leq m$	Находите $i \geq 0$, что $x_1 x_2^i x_3 x_4^i x_5 \notin L$

Вы выигрываете (и $L$ не КС), если всегда можете подобрать «побеждающее» $i$.

1.12.4 Классический пример: $L = \{a^n b^n c^n \mid n \in \mathbb{N}\}$

Утверждение: $L = \{a^n b^n c^n \mid n \geq 0\}$ не распознаётся никаким PDA.

Набросок доказательства: пусть $m \geq 1$. Возьмём $w = a^m b^m c^m \in L$ (тогда $|w| = 3m \geq m$). Для любого разбиения $w = x_1 x_2 x_3 x_4 x_5$ с $|x_2 x_4| > 0$ и $|x_2 x_3 x_4| \leq m$:

Расстояние от первого a до последнего c равно $3m$, но $|x_2 x_3 x_4| \leq m$. Значит $x_2 x_3 x_4$ не может одновременно охватывать все три типа символов — там не более двух типов (только a, только b, только c, или a+b, или b+c).

Во всех случаях накачка при $i = 2$ даёт строку с «сломанными» счётчиками:

Если $x_2 x_4$ содержит только a: при накачке добавляются a, но не b и не c, получаем $a^{m+k} b^m c^m \notin L$.
Если только b: аналогично $a^m b^{m+k} c^m \notin L$.
Если только c: $a^m b^m c^{m+k} \notin L$.
Если $x_2 x_4$ пересекает a и b: добавляются a и b, но не c — строка не в $L$.
Если $x_2 x_4$ пересекает b и c: добавляются b и c, но не a — та же проблема.

Итак, во всех случаях $x_1 x_2^2 x_3 x_4^2 x_5 \notin L$. Следовательно $L$ не контекстно-свободен. $\square$

1.13 За пределами PDA: пределы КС-языков

Не все языки — КС. Канонический пример — $L = \{a^n b^n c^n \mid n \geq 0\}$. Чтобы его распознать, нужно сравнивать три счётчика одновременно, а стек поддерживает по сути один «линейный» счёт.

Для таких языков нужна более сильная модель — машина Тьюринга с полноценной лентой чтения/записи. Стек — деструктивная память: после pop символ исчезает. Лента персистентна: чтение не разрушает символ.

Иерархия языков повторяет иерархию машин:

Регулярные — FSA
Контекстно-свободные — PDA (память стека)
Контекстно-зависимые и далее — машины Тьюринга (память ленты)

2. Определения

Автомат с магазином (PDA): модель с конечным управлением, входной лентой и неограниченным стеком. Формально — 7-кортеж $(Q, I, \Gamma, \delta, q_0, Z_0, F)$. PDA распознают ровно класс КС-языков.
Детерминированный PDA (DPDA): PDA, где (1) $|\delta(q, x, \gamma)| \leq 1$ для всех $q, x, \gamma$ (на шаг не больше одного перехода), и (2) из $\delta(q, x, \gamma) \neq \emptyset$ следует $\delta(q, \varepsilon, \gamma) = \emptyset$ для всех $x \in I$ (нет конфликта между чтением входа и $\varepsilon$-переходами).
Недетерминированный PDA: $\delta(q, a, A)$ может содержать несколько исходов. Авомат принимает, если существует последовательность выборов, ведущая к принятию.
Стек: структура LIFO — основная память PDA. Операции: push (положить наверх) и pop (снять сверху).
Алфавит магазина ($\Gamma$): конечное множество символов на стеке. Обычно включает маркер дна $Z_0$.
Символ дна стека ($Z_0$): специальный символ внизу стека изначально. Никогда не удаляется и не дублируется. Когда он сверху, стек «пуст».
Входной алфавит ($I$): конечное множество символов входной ленты. Смысл отделён от $\Gamma$, хотя множества могут пересекаться.
Функция переходов ($\delta$): $\delta: Q \times (I \cup \{\varepsilon\}) \times \Gamma \to \mathcal{P}(Q \times \Gamma^*)$. Переход $(q', \alpha) \in \delta(q, a, A)$: из $q$, читая $a$ (или $\varepsilon$) и вершину $A$, перейти в $q'$ и заменить $A$ на $\alpha$.
$\varepsilon$-переход: переход $\delta(q, \varepsilon, A) = (q', \alpha)$ без чтения входа — меняются состояние и/или стек «спонтанно».
Правило про $\varepsilon$ (условие DPDA): если из $q$ есть $\varepsilon$-переход при вершине $Z$, то не должно быть перехода с чтением входа из того же $q$ при той же вершине $Z$.
Конфигурация: тройка $(q, x, \gamma)$ — снимок PDA: состояние $q$, непрочитанный вход $x$, стек $\gamma$ (сверху вниз). Также «мгновенное описание PDA».
Переход между конфигурациями ($\vdash$): один шаг. $(q, ax, A\beta) \vdash (q', x, \alpha\beta)$ если $\delta(q, a, A) = (q', \alpha)$; либо $(q, x, A\beta) \vdash (q', x, \alpha\beta)$ если $\delta(q, \varepsilon, A) = (q', \alpha)$.
Рефлексивно-транзитивное замыкание ($\vdash^*$): $c_1 \vdash^* c_k$ — ноль или более шагов от $c_1$ к $c_k$.
Принятие финальным состоянием: $x$ принимается, если $(q_0, x, Z_0) \vdash^* (q, \varepsilon, \gamma)$ для некоторых $q \in F$, $\gamma \in \Gamma^*$. Финальный стек не важен.
Принятие пустым стеком: $x$ принимается, если $(q_0, x, Z_0) \vdash^* (q, \varepsilon, Z_0)$ для некоторого $q$ (не обязательно из $F$). Для DPDA два режима не эквивалентны.
Контекстно-свободный язык (КС, CFL): язык, распознаваемый PDA, или эквивалентно порождённый КС-грамматикой. Каждый регулярный — КС, обратное неверно.
Лемма о накачке (регулярные языки): если $L$ регулярен, существует $m \geq 1$ такое, что каждое $w \in L$ с $|w| \geq m$ раскладывается $w=xyz$, $|y| \geq 1$, $|xy| \leq m$, и $\forall i \geq 0: xy^i z \in L$.
Лемма Бар-Хиллеля (КС): если $L$ КС, существует $m \geq 1$ такое, что каждое $w \in L$ с $|w| \geq m$ раскладывается $w=x_1x_2x_3x_4x_5$, $|x_2x_4|>0$, $|x_2x_3x_4|\leq m$, и $\forall i\geq 0: x_1x_2^ix_3x_4^ix_5 \in L$.
Компилятор: программа, переводящая исходный код одного языка (например, C) в другой (например, машинный), обычно через фазы: лексика, синтаксик, семантика, генерация кода.
Лексический анализ: первая фаза; делит текст на токены. Использует FSA (регулярные шаблоны).
Синтаксический анализ (парсинг): вторая фаза; проверяет соответствие грамматике и строит дерево разбора. Использует PDA для вложенных структур.
Токен (лексема): минимальная осмысленная единица языка (например, идентификатор sum, оператор +, ключевое слово if). Выделяется на лексике.
Дерево разбора (синтаксическое дерево): дерево грамматической структуры; листья — токены; внутренние узлы — правила.
Абстрактное синтаксическое дерево (AST): упрощённое дерево для семантики, оптимизации и генерации.
Беспрефиксный язык: в $L$ ни одна строка не является собственным префиксом другой. Языки, принимаемые DPDA пустым стеком, должны быть беспрефиксными.

3. Формулы

Формальное определение PDA: $P = (Q, I, \Gamma, \delta, q_0, Z_0, F)$ где $\delta: Q \times (I \cup \{\varepsilon\}) \times \Gamma \to \mathcal{P}(Q \times \Gamma^*)$
Запись перехода: $a,\, A / \alpha$ — прочитать $a$ с входа (или $\varepsilon$), снять $A$, положить $\alpha$
Push $B$: заменить верх $A$ на $BA$ — запись $A / BA$
Pop верхнего $A$: $A / \varepsilon$
Стек не менять: $A / A$
Условие DPDA 1: $|\delta(q, x, \gamma)| \leq 1$ для всех $q \in Q$, $x \in I \cup \{\varepsilon\}$, $\gamma \in \Gamma$
Условие DPDA 2: $\delta(q, x, \gamma) \neq \emptyset \Rightarrow \delta(q, \varepsilon, \gamma) = \emptyset$ для всех $q \in Q$, $x \in I$, $\gamma \in \Gamma$
Конфигурация: $(q, x, \gamma)$ где $q \in Q$, $x \in I^*$ (остаток входа), $\gamma \in \Gamma^*$ (стек, сверху вниз)
Переход (чтение входа): $(q, ax, A\beta) \vdash (q', x, \alpha\beta)$ при $\delta(q, a, A) = (q', \alpha)$
Переход ($\varepsilon$): $(q, x, A\beta) \vdash (q', x, \alpha\beta)$ при $\delta(q, \varepsilon, A) = (q', \alpha)$
Принятие финальным состоянием: $x \in L(M) \iff (q_0, x, Z_0) \vdash^* (q, \varepsilon, \gamma)$ для некоторых $q \in F$, $\gamma \in \Gamma^*$
Распознаваемый язык: $L(M) = \{x \in I^* \mid (q_0, x, Z_0) \vdash^* (q, \varepsilon, \gamma),\; q \in F,\; \gamma \in \Gamma^*\}$
Лемма (регулярные): $L$ регулярен $\Rightarrow$ $\exists m \geq 1$: $\forall w \in L$, $|w| \geq m$, $\exists$ разбиение $w = xyz$, $|y| \geq 1$, $|xy| \leq m$, $\forall i \geq 0: xy^i z \in L$
Лемма Бар-Хиллеля (КС): $L$ КС $\Rightarrow$ $\exists m \geq 1$: $\forall w \in L$, $|w| \geq m$, $\exists$ разбиение $w = x_1x_2x_3x_4x_5$, $|x_2x_4| > 0$, $|x_2x_3x_4| \leq m$, $\forall i \geq 0: x_1x_2^ix_3x_4^ix_5 \in L$
Контрапозиция (Бар-Хиллель): $L$ не КС, если $\forall m \geq 1$ $\exists w \in L$, $|w| \geq m$, такое что $\forall$ разбиений $x_1x_2x_3x_4x_5 = w$ с $|x_2x_4| > 0$ и $|x_2x_3x_4| \leq m$: $\exists i \geq 0$ с $x_1x_2^ix_3x_4^ix_5 \notin L$

4. Примеры

4.1. Построить DPDA для $L = \{a^n b^{2n} \mid n \geq 1\}$ (Лаба 6, Задание 1)

Постройте DPDA, распознающий язык $L = \{a^n b^{2n} \mid n \geq 1\}$ — $n$ символов a, затем ровно $2n$ символов b.

Показать решение

Идея: на каждый прочитанный a нужно положить два символа стека (тогда для $n$ символов a накопится $2n$ символов). Затем снимать по одному на каждый b. Когда все b прочитаны и на стеке только $Z_0$, соотношение $1:2$ выполнено.

DPDA для aⁿb²ⁿ

Спецификация PDA:
- Состояния: $q_0$ (старт), $q_1$ (чтение a), $q_2$ (чтение b), $q_3$ (принятие)
- Алфавит стека: $\Gamma = \{Z_0, A\}$

Переходы:

Переход	Запись	Смысл
$q_0 \to q_1$	$a,\, Z_0 / AAZ_0$	Первый `a`: положить два $A$
$q_1 \circlearrowleft$	$a,\, A / AAA$	Каждый следующий `a`: положить ещё два $A$ (чисто: заменить верхний $A$ на $AAA$, добавляя два)
$q_1 \to q_2$	$b,\, A / \varepsilon$	Первый `b`: pop один $A$
$q_2 \circlearrowleft$	$b,\, A / \varepsilon$	Каждый следующий `b`: pop $A$
$q_2 \to q_3$	$\varepsilon,\, Z_0 / Z_0$	Все $A$ сняты; принять

Замечание про шаг push: при чтении a при вершине $A$ заменяем $A$ на $AAA$ — фактически сохраняем имеющийся $A$ и добавляем два сверху, то есть стек растёт на два на каждый a. Эквивалентно: каждый a должен добавить два символа — замена $A \to AAA$ (плюс два) даёт соотношение $2:1$.

Трассировка для "abb" ($n=1$, $2n=2$):
- $q_0 \xrightarrow{a,\,Z_0/AAZ_0} q_1$: стек = $A, A, Z_0$
- $q_1 \xrightarrow{b,\,A/\varepsilon} q_2$: стек = $A, Z_0$
- $q_2 \xrightarrow{b,\,A/\varepsilon} q_2$: стек = $Z_0$
- $q_2 \xrightarrow{\varepsilon,\,Z_0/Z_0} q_3$: ПРИНЯТО $\checkmark$

Трассировка для "aabbbb" ($n=2$, $2n=4$):

$q_0 \xrightarrow{a,\,Z_0/AAZ_0} q_1$: стек = $A,A,Z_0$
$q_1 \xrightarrow{a,\,A/AAA} q_1$: стек = $A,A,A,Z_0$ (чисто +2: $A \to AAA$ добавляет два)
$q_1 \xrightarrow{b,\,A/\varepsilon} q_2$: стек = $A,A,Z_0$
$q_2 \xrightarrow{b,\,A/\varepsilon} q_2$: стек = $A,Z_0$
$q_2 \xrightarrow{b,\,A/\varepsilon} q_2$: стек = $Z_0$
$q_2 \xrightarrow{b,\,A/\varepsilon} q_2$: стек = — (ОШИБКА: недостаток стека — неверно, перепроверить)

Исправление: пересчитаем. Для $n=2$: после первого a стек $AA Z_0$, затем заменяем верхний $A$ на $AAA$ для второго a: стек $A,A,A,Z_0$ (это 3 символа $A$ + $Z_0$). Нужно $2\cdot 2 = 4$ маркера для $n=2$.

Другой подход: аккуратнее: на каждый a класть ровно два $A$, используя отдельное состояние для второго push.

Переход	Запись	Смысл
$q_0 \to q_1$	$a,\, Z_0 / AZ_0$	Первый `a`: первый $A$
$q_1 \to q_2$	$\varepsilon,\, A / AA$	Спонтанно: второй $A$
$q_2 \to q_2$	$a,\, A / AA$	Следующий `a` (первый из пары push)
…	…	…

Самый простой корректный вариант: на каждый a — два $A$ через вспомогательное состояние:

Состояния: $q_0$ (старт), $q_1$ (только что прочитан a, нужен второй $A$), $q_2$ (готовы читать a или b), $q_3$ (чтение b), $q_4$ (принятие)

Переход	Запись	Смысл
$q_0 \to q_1$	$a,\, Z_0 / AZ_0$	Первый `a`: один $A$
$q_1 \to q_2$	$\varepsilon,\, A / AA$	Второй $A$ (спонтанно)
$q_2 \to q_1$	$a,\, A / AA$	Ещё `a`: первый из двух $A$
$q_2 \to q_3$	$b,\, A / \varepsilon$	Начало `b`: pop один $A$
$q_3 \circlearrowleft$	$b,\, A / \varepsilon$	Каждый `b`: pop $A$
$q_3 \to q_4$	$\varepsilon,\, Z_0 / Z_0$	«Пустой» стек: принять

Ответ: DPDA с вспомогательным состоянием для второго $A$ на каждый a, затем pop по одному $A$ на каждый b, распознаёт $L = \{a^n b^{2n} \mid n \geq 1\}$.

4.2. Построить DPDA для скобок арифметических выражений (Лаба 6, Домашнее задание 1)

Постройте DPDA, распознающий язык корректных скобок арифметических выражений (бинарные операции). Алфавит $I = \{a, (, ), +\}$, где $a$ — термы, а + — бинарный оператор.

Примеры в языке: (a + a), ((a) + (a + a)), ((a + a)) Язык — синтаксически корректные выражения со скобочными подвыражениями.

Показать решение

Идея: задача про простую грамматику выражений. Главное ограничение — баланс скобок: каждой ( нужна ), вложенность корректна. Символы $a$ и + в этой упрощённой постановке — «наполнитель», не ломающий баланс.

Каркас DPDA для сбалансированных скобок в арифметических выражениях

Упрощение: для построения DPDA достаточно свойства баланса скобок. Символы $a$ и + должны появляться в допустимых позициях грамматики; моделируем это, отслеживая открытые скобки на стеке.

Грамматика (неформально):

Выражение: терм, или ( выражение ), или выражение + выражение

В простом DPDA, отслеживающем только баланс скобок:

Состояния: $q_0$ (работа), $q_1$ (принятие)
- Алфавит стека: $\Gamma = \{Z_0, P\}$, где $P$ маркирует открытую (

Переходы (петли на $q_0$):

Запись	Смысл
$(,\, Z_0 / PZ_0$	Открыли `(` при «пустом» стеке: push $P$
$(,\, P / PP$	`(` внутри другой: push $P$
$),\, P / \varepsilon$	Закрыли `)`: снять парный $P$
$a,\, Z_0 / Z_0$	Прочитали терм $a$: стек не меняем
$a,\, P / P$	Терм $a$ внутри скобок: стек не меняем
$+,\, Z_0 / Z_0$	Оператор вне скобок: стек не меняем
$+,\, P / P$	Оператор внутри скобок: стек не меняем

Принятие: $q_0 \to q_1$: $\varepsilon,\, Z_0 / Z_0$ — баланс.
Трассировка для "(a+a)":
- $q_0 \xrightarrow{(,\,Z_0/PZ_0} q_0$: стек = $P, Z_0$
- $q_0 \xrightarrow{a,\,P/P} q_0$: стек = $P, Z_0$
- $q_0 \xrightarrow{+,\,P/P} q_0$: стек = $P, Z_0$
- $q_0 \xrightarrow{a,\,P/P} q_0$: стек = $P, Z_0$
- $q_0 \xrightarrow{),\,P/\varepsilon} q_0$: стек = $Z_0$
- $q_0 \xrightarrow{\varepsilon,\,Z_0/Z_0} q_1$: ПРИНЯТО $\checkmark$

Ответ: DPDA отслеживает баланс скобок стеком и принимает, когда скобки согласованы и вход полностью прочитан.

**4.3. Построить DPDA для $P = \{xycy^Rx^R \mid x \in \{a,b\}^, y \in \{d,e\}^, |x|>0\}$** (Лаба 6, Задание 2)

Постройте DPDA для $P = \{xycy^Rx^R \mid x \in \{a,b\}^*, y \in \{d,e\}^*, |x|>0\}$ над алфавитом $I = \{a,b,c,d,e\}$.

(Строка: непустая $x$ над $\{a,b\}$, затем $y$ над $\{d,e\}$, маркер $c$, затем $y^R$, затем $x^R$.)

Показать решение

Идея: положить на стек все символы $x$ (для a — $A$, для b — $B$), затем все символы $y$ (для d — $D$, для e — $E$). При появлении $c$ перейти в режим pop: сначала согласовать $y^R$ (обращение $y$), затем $x^R$.

Спецификация PDA:
- Состояния: $q_0$ (push $x$), $q_1$ (push $y$), $q_2$ (pop $y^R$), $q_3$ (pop $x^R$), $q_4$ (принятие)
- Алфавит стека: $\Gamma = \{Z_0, A, B, D, E\}$
Фаза 1 — push $x$ (состояние $q_0$, петли):
- $a,\, Z_0 / AZ_0$; $b,\, Z_0 / BZ_0$
- $a,\, A / AA$; $a,\, B / AB$
- $b,\, A / BA$; $b,\, B / BB$
Переход к фазе push $y$ ($q_0 \to q_1$): при первом d или e перейти в $q_1$:
- $d,\, A / DA$; $d,\, B / DB$; $e,\, A / EA$; $e,\, B / EB$
Фаза 2 — push $y$ ($q_1$, петли):
- $d,\, D / DD$; $d,\, E / DE$
- $e,\, D / ED$; $e,\, E / EE$
Опора на $c$ ($q_1 \to q_2$ или $q_0 \to q_2$, если $y$ пусто):
- $c,\, D / D$; $c,\, E / E$ (верх — символ $y$: фаза pop-$y$)
- $c,\, A / A$; $c,\, B / B$ ($y$ не было: сразу pop-$x$: $q_1 \to q_3$)
Фаза 3 — pop $y^R$ ($q_2$, петли):
- $d,\, D / \varepsilon$; $e,\, E / \varepsilon$ (сопоставление $d \leftrightarrow D$, $e \leftrightarrow E$)
- Переход к pop-$x$, когда на вершине $A$ или $B$: $q_2 \to q_3$ на $\varepsilon$: $\varepsilon,\, A / A$; $\varepsilon,\, B / B$
Фаза 4 — pop $x^R$ ($q_3$, петли):
- $a,\, A / \varepsilon$; $b,\, B / \varepsilon$
Принятие: $q_3 \to q_4$: $\varepsilon,\, Z_0 / Z_0$

Ответ: DPDA с фазами push $x$, push $y$, pop $y^R$, pop $x^R$ (с опорой $c$) распознаёт $P$.

4.4. Построить DPDA для сбалансированных круглых и квадратных скобок (Лаба 6, Задание 3)

Постройте DPDA для языка вложенных сбалансированных скобок над алфавитом $I = \{(, ), [, ]\}$.

Примеры в языке: (([])())(), (())[] Примеры не в языке: ([(]))()(), ([)]

Показать решение

Идея: стек хранит открытые разделители. Для ( кладём маркер $P$, для [ — $Q$. При ) снимаем верх и проверяем, что это $P$. При ] — что верх $Q$. Принимаем, когда вход кончился и на стеке только $Z_0$.

DPDA для сбалансированных круглых и квадратных скобок

Замечание: важно отвергнуть ([)] — закрывающие символы должны соответствовать последнему открытию. LIFO стека обеспечивает это естественно.

Спецификация:
- Состояния: $q_0$ (старт, работа), $q_1$ (принятие)
- Алфавит стека: $\Gamma = \{Z_0, P, Q\}$, где $P$ для (, $Q$ для [

Переходы (петли на $q_0$, кроме финального перехода принятия):

Запись	Смысл
$(,\, Z_0 / PZ_0$	`(` при пустом стеке: push $P$
$(,\, P / PP$	`(` при вершине $P$: push $P$
$(,\, Q / PQ$	`(` при вершине $Q$: push $P$
$[,\, Z_0 / QZ_0$	`[` при пустом стеке: push $Q$
$[,\, P / QP$	`[` при вершине $P$: push $Q$
$[,\, Q / QQ$	`[` при вершине $Q$: push $Q$
$),\, P / \varepsilon$	`)` при вершине $P$: pop (совпало)
$],\, Q / \varepsilon$	`]` при вершине $Q$: pop (совпало)

Принятие: $q_0 \to q_1$: $\varepsilon,\, Z_0 / Z_0$ — всё согласовано, только $Z_0$.
Отклонение (неявно): если читается ), а сверху $Q$, перехода нет — автомат застревает и отвергает. Так корректно отвергается ([)].
Трассировка для "([])":
- $q_0 \xrightarrow{(,\,Z_0/PZ_0} q_0$: стек = $P, Z_0$
- $q_0 \xrightarrow{[,\,P/QP} q_0$: стек = $Q, P, Z_0$
- $q_0 \xrightarrow{],\,Q/\varepsilon} q_0$: стек = $P, Z_0$
- $q_0 \xrightarrow{),\,P/\varepsilon} q_0$: стек = $Z_0$
- $q_0 \xrightarrow{\varepsilon,\,Z_0/Z_0} q_1$: ПРИНЯТО $\checkmark$

Ответ: приведённый DPDA распознаёт язык вложенных сбалансированных скобок над $\{(, ), [, ]\}$.

**4.5. Построить DPDA для $L_1 = \{w \in \{a,b\}^* \mid \phi(w,a) = \phi(w,b)\}$** (Лаба 6, Задание 4)

Постройте DPDA для $L_1 = \{w \in \{a,b\}^* \mid \phi(w,a) = \phi(w,b)\}$, где $\phi(s,c)$ — число вхождений символа $c$ в строку $s$. Иначе говоря, $L_1$ — все строки над $\{a,b\}$ с равным числом a и b (в любом порядке).

Показать решение

Идея: в отличие от $a^n b^n$, здесь a и b могут чередоваться как угодно. Стек используем как счётчик: кладём $A$ за каждый a (когда стек только $Z_0$ или только $A$), и $B$ за каждый b (когда только $Z_0$ или только $B$). Если входной символ «гасит» вершину (a при вершине $B$ или b при вершине $A$), делаем pop. Это чистый баланс.

Спецификация:
- Состояния: $q_0$ (работа), $q_1$ (принятие)
- Алфавит стека: $\Gamma = \{Z_0, A, B\}$
- $A$ на стеке — «лишние a»; $B$ — «лишние b»

Переходы (петли на $q_0$):

Запись	Смысл
$a,\, Z_0 / AZ_0$	`a` при балансе: push $A$ (+1 к `a`)
$a,\, A / AA$	`a` при избытке `a`: ещё $A$
$a,\, B / \varepsilon$	`a` при избытке `b`: снять один $B$
$b,\, Z_0 / BZ_0$	`b` при балансе: push $B$
$b,\, B / BB$	`b` при избытке `b`: ещё $B$
$b,\, A / \varepsilon$	`b` при избытке `a`: снять один $A$

Принятие: $q_0 \to q_1$: $\varepsilon,\, Z_0 / Z_0$ — всё сократилось до $Z_0$: счётчики равны.
Трассировка для "abba":
- $q_0 \xrightarrow{a,\,Z_0/AZ_0} q_0$: стек = $A, Z_0$ (избыток a = 1)
- $q_0 \xrightarrow{b,\,A/\varepsilon} q_0$: стек = $Z_0$ (сокращение)
- $q_0 \xrightarrow{b,\,Z_0/BZ_0} q_0$: стек = $B, Z_0$ (избыток b = 1)
- $q_0 \xrightarrow{a,\,B/\varepsilon} q_0$: стек = $Z_0$
- $q_0 \xrightarrow{\varepsilon,\,Z_0/Z_0} q_1$: ПРИНЯТО $\checkmark$
Трассировка для "aab" (должно отвергаться: $\phi(w,a)=2 \neq 1=\phi(w,b)$):
- $q_0 \xrightarrow{a,\,Z_0/AZ_0} q_0$: стек = $A, Z_0$
- $q_0 \xrightarrow{a,\,A/AA} q_0$: стек = $A, A, Z_0$
- $q_0 \xrightarrow{b,\,A/\varepsilon} q_0$: стек = $A, Z_0$
- Вход кончился; стек $A, Z_0$ (не только $Z_0$); $\varepsilon$-перехода принятия нет. ОТВЕРГНУТО $\checkmark$

Ответ: приведённый DPDA использует стек как знаковый счётчик и распознаёт $L_1 = \{w \mid \phi(w,a) = \phi(w,b)\}$.

4.6. Построить DPDA для $L_2 = \{a^n b^m a^m b^n \mid n > 0, m > 0\}$ (Лаба 6, Задание 5)

Постройте DPDA для $L_2 = \{a^n b^m a^m b^n \mid n > 0, m > 0\}$.

Показать решение

Идея: строка вида $a^n b^m a^m b^n$ — внешний слой a, внутренний слой b, согласованный внутренний слой a, согласованный внешний слой b. Стек в двух фазах:

DPDA для aⁿbᵐaᵐbⁿ

Фаза 1 (внешние a): положить $n$ копий $A$ для ведущих a.
Фаза 2 (внутренние b): положить $m$ копий $B$ поверх $A$.
Фаза 3 (внутренние a): снять по одному $B$ на каждый a (согласование внутренних b и a).
Фаза 4 (внешние b): снять по одному $A$ на каждый b (согласование внешних a и b).

Состояния: $q_0$ (внешние a), $q_1$ (внутренние b), $q_2$ (внутренние a), $q_3$ (внешние b), $q_4$ (принятие)

Переходы:

Переход	Запись	Смысл
$q_0 \circlearrowleft$	$a,\, Z_0 / AZ_0$	Первый внешний `a`: push $A$
$q_0 \circlearrowleft$	$a,\, A / AA$	Ещё внешние `a`: push $A$
$q_0 \to q_1$	$b,\, A / BA$	Первый внутренний `b`: push $B$ над $A$
$q_1 \circlearrowleft$	$b,\, B / BB$	Ещё внутренние `b`: push $B$
$q_1 \to q_2$	$a,\, B / \varepsilon$	Первый внутренний `a`: pop $B$
$q_2 \circlearrowleft$	$a,\, B / \varepsilon$	Ещё внутренние `a`: pop $B$
$q_2 \to q_3$	$b,\, A / \varepsilon$	Первый внешний `b`: pop $A$ (все $B$ сняты)
$q_3 \circlearrowleft$	$b,\, A / \varepsilon$	Ещё внешние `b`: pop $A$
$q_3 \to q_4$	$\varepsilon,\, Z_0 / Z_0$	Всё согласовано: принять

Трассировка для "abba" слишком коротка (минимум $a^1b^1a^1b^1 = "abab"$):

Трассировка для "abab" ($n=m=1$):
- $q_0 \xrightarrow{a,\,Z_0/AZ_0} q_0$: стек = $A, Z_0$
- $q_0 \xrightarrow{b,\,A/BA} q_1$: стек = $B, A, Z_0$
- $q_1 \xrightarrow{a,\,B/\varepsilon} q_2$: стек = $A, Z_0$
- $q_2 \xrightarrow{b,\,A/\varepsilon} q_3$: стек = $Z_0$
- $q_3 \xrightarrow{\varepsilon,\,Z_0/Z_0} q_4$: ПРИНЯТО $\checkmark$

Ответ: DPDA с фазами внешних a, внутренних b, внутренних a, внешних b распознаёт $L_2$.

4.7. Доказать, что $L = \{a^n b^n c^n \mid n \in \mathbb{N}\}$ не КС (Туториал 6, Пример 1)

Докажите леммой Бар-Хиллеля (леммой о накачке для КС-языков), что $L = \{a^n b^n c^n \mid n \geq 0\}$ не является контекстно-свободным языком.

Показать решение

Идея: в $L$ числа a, b и c должны совпадать. Лемма Бар-Хиллеля накачивает два отрезка синхронно, но любое «окно» длины $\leq m$ внутри $a^m b^m c^m$ охватывает не больше двух типов символов. Накачка ломает хотя бы один счётчик.

От противного: пусть $L$ КС. Пусть $m \geq 1$ — длина накачки из леммы Бар-Хиллеля.
Слово: $w = a^m b^m c^m \in L$, $|w| = 3m \geq m$.
Любое разбиение $w = x_1 x_2 x_3 x_4 x_5$ с $|x_2 x_4| > 0$ и $|x_2 x_3 x_4| \leq m$.
Где может лежать $x_2 x_3 x_4$: расстояние от первого a до последнего c равно $3m - 1$. Так как $|x_2 x_3 x_4| \leq m < 3m$, окно не может одновременно покрыть все три типа. Возможны:
- только a, или только b, или только c, или
- a+b (без c), или b+c (без a)
Накачка при $i = 2$: рассмотрим $x_1 x_2^2 x_3 x_4^2 x_5$. Во всех случаях:
- Если $x_2 x_4$ только из a: добавляются a, не b и не c — больше a, чем b и c. $\notin L$.
- Если только из b: аналогично $\notin L$.
- Если только из c: $\notin L$.
- Если $x_2 x_4$ пересекает a и b: добавляются a и b, не c. $\notin L$.
- Если пересекает b и c: добавляются b и c, не a. $\notin L$.
Вывод: во всех случаях $x_1 x_2^2 x_3 x_4^2 x_5 \notin L$ — противоречие с леммой. Значит $L$ не КС. $\square$

Ответ: $L = \{a^n b^n c^n \mid n \geq 0\}$ не контекстно-свободен.

4.8. Построить DPDA для $L_1 = \{a^n b^n \mid n \geq 1\}$ (Туториал 6, Пример 2)

Постройте DPDA для $L_1 = \{a^n b^n \mid n \geq 1\}$ и выполните трассировку на входе "aabb".

Показать решение

Идея: считать a стеком: по одному $A$ на каждый a, затем по одному pop на каждый b. Если после всех b на стеке только $Z_0$, длины совпали.

DPDA для трассировки aⁿbⁿ

Спецификация PDA:
- Состояния: $p_0$ (старт), $p_1$ (чтение a), $p_2$ (чтение b), $p_3$ (принятие)
- Алфавит стека: $\Gamma = \{Z_0, A\}$
- Входной алфавит: $I = \{a, b\}$

Переходы:

Переход	Запись	Смысл
$p_0 \to p_1$	$a,\, Z_0 / AZ_0$	Первый `a`; push $A$ над $Z_0$
$p_1 \circlearrowleft$	$a,\, A / AA$	Дополнительные `a`; каждый раз push $A$
$p_1 \to p_2$	$b,\, A / \varepsilon$	Первый `b`; pop один $A$
$p_2 \circlearrowleft$	$b,\, A / \varepsilon$	Дополнительные `b`; каждый раз pop $A$
$p_2 \to p_3$	$\varepsilon,\, Z_0 / Z_0$	Вход кончился; сверху $Z_0$ — все $A$ совпали; принять

Проверка детерминизма:
- У каждого $\delta$ не больше одного исхода — условие 1.
- $\varepsilon$-переход $\delta(p_2, \varepsilon, Z_0) = (p_3, Z_0)$ использует вершину $Z_0$. Из $p_2$ нет читающего вход перехода при вершине $Z_0$ — условие 2.

Трассировка для "aabb":

Шаг	Состояние	Непрочитанный вход	Стек	Правило
1	$p_0$	$\mathbf{a}abb$	$Z_0$	$a,\,Z_0/AZ_0$: push $A$
2	$p_1$	$\mathbf{a}bb$	$A, Z_0$	$a,\,A/AA$: push $A$
3	$p_1$	$\mathbf{b}b$	$A, A, Z_0$	$b,\,A/\varepsilon$: pop $A$
4	$p_2$	$\mathbf{b}$	$A, Z_0$	$b,\,A/\varepsilon$: pop $A$
5	$p_2$	$\varepsilon$	$Z_0$	$\varepsilon,\,Z_0/Z_0$: к принятию
6	$p_3$	$\varepsilon$	$Z_0$	ПРИНЯТО $\checkmark$

Полная цепочка конфигураций: \[(p_0, aabb, Z_0) \vdash (p_1, abb, AZ_0) \vdash (p_1, bb, AAZ_0) \vdash (p_2, b, AZ_0) \vdash (p_2, \varepsilon, Z_0) \vdash (p_3, \varepsilon, Z_0)\]

Ответ: DPDA с состояниями $p_0, p_1, p_2, p_3$ (принимающее) и указанными переходами распознаёт $L_1 = \{a^n b^n \mid n \geq 1\}$.

4.9. Построить DPDA для $L_2 = \{a^n b a^n \mid n \in \mathbb{N}^+\}$ (Туториал 6, Пример 3)

Постройте DPDA для $L_2 = \{a^n b a^n \mid n \geq 1\}$.

Показать решение

Идея: по одному $A$ на каждый a до единственного b. Символ b — опора: переключение из режима push в pop. После b — по одному pop на каждый a справа. Равенство чисел a слева и справа.

Спецификация:
- Состояния: $q_0$ (старт, фаза push), $q_1$ (фаза pop после b), $q_2$ (принятие)
- Алфавит стека: $\Gamma = \{Z_0, A\}$

Переходы:

Переход	Запись	Смысл
$q_0 \circlearrowleft$	$a,\, Z_0 / AZ_0$	Первый `a` до `b`: push $A$
$q_0 \circlearrowleft$	$a,\, A / AA$	Каждый следующий `a` до `b`: push $A$
$q_0 \to q_1$	$b,\, A / A$	Прочитали `b`: стек не меняем, переход в pop
$q_1 \circlearrowleft$	$a,\, A / \varepsilon$	Каждый `a` после `b`: pop $A$
$q_1 \to q_2$	$\varepsilon,\, Z_0 / Z_0$	Все $A$ совпали; принять

Трассировка для "aba":
- $q_0 \xrightarrow{a,\,Z_0/AZ_0} q_0$: стек = $A, Z_0$
- $q_0 \xrightarrow{b,\,A/A} q_1$: стек = $A, Z_0$ (без изменений)
- $q_1 \xrightarrow{a,\,A/\varepsilon} q_1$: стек = $Z_0$
- $q_1 \xrightarrow{\varepsilon,\,Z_0/Z_0} q_2$: ПРИНЯТО $\checkmark$
Трассировка для "aabaa":
- $q_0 \xrightarrow{a,\,Z_0/AZ_0} q_0$: стек = $A, Z_0$
- $q_0 \xrightarrow{a,\,A/AA} q_0$: стек = $A, A, Z_0$
- $q_0 \xrightarrow{b,\,A/A} q_1$: стек = $A, A, Z_0$
- $q_1 \xrightarrow{a,\,A/\varepsilon} q_1$: стек = $A, Z_0$
- $q_1 \xrightarrow{a,\,A/\varepsilon} q_1$: стек = $Z_0$
- $q_1 \xrightarrow{\varepsilon,\,Z_0/Z_0} q_2$: ПРИНЯТО $\checkmark$

Ответ: DPDA с состояниями $q_0, q_1, q_2$ (принимающее) и указанными переходами распознаёт $L_2 = \{a^n b a^n \mid n \geq 1\}$.

**4.10. Построить DPDA для $L_3 = \{vcv^R \mid v \in \{a,b\}^*\}$** (Туториал 6, Пример 4)

Постройте DPDA для $L_3 = \{vcv^R \mid v \in \{a,b\}^*\}$, где $v^R$ — обращение $v$, а $c$ — особый разделитель. Входной алфавит $I = \{a, b, c\}$.

Показать решение

Идея: положить на стек каждый символ $v$ (для a — $A$, для b — $B$). Увидев центральный $c$, перейти в режим pop и согласовывать $v^R$ со стеком. Так как $v^R$ — обращение $v$, сверху вниз стек должен совпасть с $v^R$.

Спецификация:
- Состояния: $q_0$ (фаза push), $q_1$ (фаза pop), $q_2$ (принятие)
- Алфавит стека: $\Gamma = \{Z_0, A, B\}$, где $A$ кодирует a, $B$ — b

Переходы:

Фаза push ($q_0$, петли):

Запись	Смысл
$a,\, Z_0 / AZ_0$	Первый `a`: push $A$
$b,\, Z_0 / BZ_0$	Первый `b`: push $B$
$a,\, A / AA$	Следующий `a` при вершине $A$: push $A$
$a,\, B / AB$	Следующий `a` при вершине $B$: push $A$
$b,\, A / BA$	Следующий `b` при вершине $A$: push $B$
$b,\, B / BB$	Следующий `b` при вершине $B$: push $B$

Опора (чтение $c$, $q_0 \to q_1$, стек не меняется):

Запись	Смысл
$c,\, Z_0 / Z_0$	$v$ пусто: перейти в pop
$c,\, A / A$	$c$ при вершине $A$: в pop
$c,\, B / B$	$c$ при вершине $B$: в pop

Фаза pop ($q_1$, петли):

Запись	Смысл
$a,\, A / \varepsilon$	`a` и вершина $A$: совпало, pop
$b,\, B / \varepsilon$	`b` и вершина $B$: совпало, pop

Принятие: $q_1 \to q_2$: $\varepsilon,\, Z_0 / Z_0$ — всё совпало.

Трассировка для "abcba" ($v = "ab"$, $v^R = "ba"$):
- $q_0 \xrightarrow{a,\,Z_0/AZ_0} q_0$: стек = $A, Z_0$
- $q_0 \xrightarrow{b,\,A/BA} q_0$: стек = $B, A, Z_0$
- $q_0 \xrightarrow{c,\,B/B} q_1$: стек = $B, A, Z_0$ (без изменений)
- $q_1 \xrightarrow{b,\,B/\varepsilon} q_1$: стек = $A, Z_0$
- $q_1 \xrightarrow{a,\,A/\varepsilon} q_1$: стек = $Z_0$
- $q_1 \xrightarrow{\varepsilon,\,Z_0/Z_0} q_2$: ПРИНЯТО $\checkmark$

Ответ: DPDA с состояниями $q_0, q_1, q_2$ (принимающее) и указанными переходами распознаёт $L_3 = \{vcv^R \mid v \in \{a,b\}^*\}$.

Переход	Запись	Смысл
\(p_0 \to p_1\)	\(a,\, Z_0 / AZ_0\)	Первый `a`; положить \(A\) над \(Z_0\)
\(p_1 \circlearrowleft\)	\(a,\, A / AA\)	Каждый следующий `a`; ещё один \(A\)
\(p_1 \to p_2\)	\(b,\, A / \varepsilon\)	Первый `b`; снять один \(A\)
\(p_2 \circlearrowleft\)	\(b,\, A / \varepsilon\)	Каждый следующий `b`; снять \(A\)
\(p_2 \to p_3\)	\(\varepsilon,\, Z_0 / Z_0\)	Вход исчерпан; сверху \(Z_0\) — значит все \(A\) совпали; принять

Шаг	Состояние	Непрочитанный вход	Стек (сверху вниз)	Правило
1	\(p_0\)	\(\mathbf{a}abb\)	\(Z_0\)	\(a,\, Z_0 / AZ_0\): push \(A\)
2	\(p_1\)	\(\mathbf{a}bb\)	\(A, Z_0\)	\(a,\, A / AA\): push \(A\)
3	\(p_1\)	\(\mathbf{b}b\)	\(A, A, Z_0\)	\(b,\, A / \varepsilon\): pop \(A\)
4	\(p_2\)	\(\mathbf{b}\)	\(A, Z_0\)	\(b,\, A / \varepsilon\): pop \(A\)
5	\(p_2\)	\(\varepsilon\)	\(Z_0\)	\(\varepsilon,\, Z_0 / Z_0\): к принятию
6	\(p_3\)	\(\varepsilon\)	\(Z_0\)	ПРИНЯТО \(\checkmark\)

Переход	Запись	Смысл
\(q_0 \circlearrowleft\)	\(a,\, Z_0 / AZ_0\)	Первый `a` до `b`: push \(A\)
\(q_0 \circlearrowleft\)	\(a,\, A / AA\)	Каждый следующий `a` до `b$: push $A$ \| \| $q_0 \to q_1$ \| $b,\, A / A$ \| Видим`b`; стек не меняем, меняем состояние \| \| $q_1 \circlearrowleft$ \| $a,\, A / \varepsilon$ \| Каждый`a`после`b`: pop один \(A\)
\(q_1 \to q_2\)	\(\varepsilon,\, Z_0 / Z_0\)	Все \(A\) совпали; принять

Игрок 1 (противник)	Игрок 2 (вы)
Выбирает любое \(m \geq 1\)	Выбираете \(w \in L\) с \(\|w\| \geq m\)
Выбирает разбиение \(w = x_1 x_2 x_3 x_4 x_5\) с \(\|x_2 x_4\| > 0\) и \(\|x_2 x_3 x_4\| \leq m\)	Находите \(i \geq 0\), что \(x_1 x_2^i x_3 x_4^i x_5 \notin L\)

Переход	Запись	Смысл
\(q_0 \to q_1\)	\(a,\, Z_0 / AAZ_0\)	Первый `a`: положить два \(A\)
\(q_1 \circlearrowleft\)	\(a,\, A / AAA\)	Каждый следующий `a`: положить ещё два \(A\) (чисто: заменить верхний \(A\) на \(AAA\), добавляя два)
\(q_1 \to q_2\)	\(b,\, A / \varepsilon\)	Первый `b`: pop один \(A\)
\(q_2 \circlearrowleft\)	\(b,\, A / \varepsilon\)	Каждый следующий `b`: pop \(A\)
\(q_2 \to q_3\)	\(\varepsilon,\, Z_0 / Z_0\)	Все \(A\) сняты; принять

W6. Детерминированные автоматы с магазином, конфигурации, лемма о накачке для КС-языков, автоматы с магазином и компиляторы

1. Краткое содержание

1.1 От конечных автоматов к автоматам с магазином

1.2 Стек: краткое напоминание

1.3 Неформальное описание PDA

1.4 Формальное определение PDA

1.5 Детерминированные автоматы с магазином (DPDA)

1.6 Конфигурации и переходы

1.6.1 Конфигурация

1.6.2 Переходы между конфигурациями

**1.6.3 Многошаговое вычисление: \(\vdash^*\)**

1.6.4 Принятие строки PDA

1.7 Два режима принятия

1.8 Разобранный пример: PDA для \(L = \{a^n b^n \mid n \geq 1\}\)

1.9 Ещё примеры PDA

1.9.1 PDA для \(L_2 = \{a^n b a^n \mid n \in \mathbb{N}^+\}\)

**1.9.2 PDA для \(L_3 = \{vcv^R \mid v \in \{a,b\}^*\}\)**

1.9.3 PDA для сбалансированных круглых скобок

1.10 PDA и FSA: общая картина

1.11 PDA и компиляторы

1.12 Лемма о накачке для КС-языков (лемма Бар-Хиллеля)

1.12.1 Лемма о накачке для регулярных языков (напоминание)

1.12.2 Лемма Бар-Хиллеля (лемма о накачке для КС-языков)

1.12.3 Контрапозиция: как доказать «не КС»

1.12.4 Классический пример: \(L = \{a^n b^n c^n \mid n \in \mathbb{N}\}\)

1.13 За пределами PDA: пределы КС-языков

2. Определения

3. Формулы

4. Примеры

4.1. Построить DPDA для \(L = \{a^n b^{2n} \mid n \geq 1\}\) (Лаба 6, Задание 1)

4.2. Построить DPDA для скобок арифметических выражений (Лаба 6, Домашнее задание 1)

**4.3. Построить DPDA для \(P = \{xycy^Rx^R \mid x \in \{a,b\}^, y \in \{d,e\}^, |x|>0\}\)** (Лаба 6, Задание 2)

4.4. Построить DPDA для сбалансированных круглых и квадратных скобок (Лаба 6, Задание 3)

**4.5. Построить DPDA для \(L_1 = \{w \in \{a,b\}^* \mid \phi(w,a) = \phi(w,b)\}\)** (Лаба 6, Задание 4)

4.6. Построить DPDA для \(L_2 = \{a^n b^m a^m b^n \mid n > 0, m > 0\}\) (Лаба 6, Задание 5)

4.7. Доказать, что \(L = \{a^n b^n c^n \mid n \in \mathbb{N}\}\) не КС (Туториал 6, Пример 1)

4.8. Построить DPDA для \(L_1 = \{a^n b^n \mid n \geq 1\}\) (Туториал 6, Пример 2)

4.9. Построить DPDA для \(L_2 = \{a^n b a^n \mid n \in \mathbb{N}^+\}\) (Туториал 6, Пример 3)

**4.10. Построить DPDA для \(L_3 = \{vcv^R \mid v \in \{a,b\}^*\}\)** (Туториал 6, Пример 4)

1. Краткое содержание

1.1 От конечных автоматов к автоматам с магазином

1.2 Стек: краткое напоминание

1.3 Неформальное описание PDA

1.4 Формальное определение PDA

1.5 Детерминированные автоматы с магазином (DPDA)

1.6 Конфигурации и переходы

1.6.1 Конфигурация

1.6.2 Переходы между конфигурациями

1.6.3 Многошаговое вычисление: \(\vdash^*\)

1.6.4 Принятие строки PDA

1.7 Два режима принятия

1.8 Разобранный пример: PDA для \(L = \{a^n b^n \mid n \geq 1\}\)

1.9 Ещё примеры PDA

1.9.1 PDA для \(L_2 = \{a^n b a^n \mid n \in \mathbb{N}^+\}\)

1.9.2 PDA для \(L_3 = \{vcv^R \mid v \in \{a,b\}^*\}\)

1.9.3 PDA для сбалансированных круглых скобок

1.10 PDA и FSA: общая картина

1.11 PDA и компиляторы

1.12 Лемма о накачке для КС-языков (лемма Бар-Хиллеля)

1.12.1 Лемма о накачке для регулярных языков (напоминание)

1.12.2 Лемма Бар-Хиллеля (лемма о накачке для КС-языков)

1.12.3 Контрапозиция: как доказать «не КС»

1.12.4 Классический пример: \(L = \{a^n b^n c^n \mid n \in \mathbb{N}\}\)

1.13 За пределами PDA: пределы КС-языков

2. Определения

3. Формулы

4. Примеры

4.1. Построить DPDA для \(L = \{a^n b^{2n} \mid n \geq 1\}\) (Лаба 6, Задание 1)

4.2. Построить DPDA для скобок арифметических выражений (Лаба 6, Домашнее задание 1)

4.3. Построить DPDA для \(P = \{xycy^Rx^R \mid x \in \{a,b\}^*, y \in \{d,e\}^*, |x|>0\}\) (Лаба 6, Задание 2)

4.4. Построить DPDA для сбалансированных круглых и квадратных скобок (Лаба 6, Задание 3)

4.5. Построить DPDA для \(L_1 = \{w \in \{a,b\}^* \mid \phi(w,a) = \phi(w,b)\}\) (Лаба 6, Задание 4)

4.6. Построить DPDA для \(L_2 = \{a^n b^m a^m b^n \mid n > 0, m > 0\}\) (Лаба 6, Задание 5)

4.7. Доказать, что \(L = \{a^n b^n c^n \mid n \in \mathbb{N}\}\) не КС (Туториал 6, Пример 1)

4.8. Построить DPDA для \(L_1 = \{a^n b^n \mid n \geq 1\}\) (Туториал 6, Пример 2)

4.9. Построить DPDA для \(L_2 = \{a^n b a^n \mid n \in \mathbb{N}^+\}\) (Туториал 6, Пример 3)

4.10. Построить DPDA для \(L_3 = \{vcv^R \mid v \in \{a,b\}^*\}\) (Туториал 6, Пример 4)

**1.6.3 Многошаговое вычисление: \(\vdash^*\)**

**1.9.2 PDA для \(L_3 = \{vcv^R \mid v \in \{a,b\}^*\}\)**

**4.3. Построить DPDA для \(P = \{xycy^Rx^R \mid x \in \{a,b\}^, y \in \{d,e\}^, |x|>0\}\)** (Лаба 6, Задание 2)

**4.5. Построить DPDA для \(L_1 = \{w \in \{a,b\}^* \mid \phi(w,a) = \phi(w,b)\}\)** (Лаба 6, Задание 4)

**4.10. Построить DPDA для \(L_3 = \{vcv^R \mid v \in \{a,b\}^*\}\)** (Туториал 6, Пример 4)